googologywikiaorg-20200223-history
User blog:Syst3ms/STON 2 : BMS and the Star
This is an attempt at extending STON. Definition Set of formal strings \(T\) Definition of \(T\): *\(0 \in T\) *For \(a,b \in T\), \(a+b\in T\) *For \(a,b \in T\), \(\psi_a(b)\in T\) *For \(a \in T\), \(\mu(a)\in T\) Shorthands Base of the notation Definition of \(PT\), the set of principal terms ''': *For \(a,b \in T\), \(\psi_a(b)\in PT\) *For \(a \in T\), \(\mu(a)\in PT\) Definition of \(ST\), the set of '''successor terms : *\(1\in ST\) *For \(a\in T\), \(a+1\in ST\) Definition of \(\text{pre}(s)\), the predecessor function : #If \(s\in \{0\}\cap PT\), \(\text{pre}(s)=0\) #Else if \(s=s_1+s_2\) with \(s_1\in PT,s_2\in T\) : ##If \(\text{pre}(s_2)=0\) then \(\text{pre}(s)=s_1\) ##Otherwise, \(\text{pre}(s)=s_1+\text{pre}(s_2)\) Definition of \(\text{cof}(s)\), the cofinality function: #If \(s=0\vee s=1\) then \(\text{cof}(s)=s\) #Else if \(0<\text{lev}(s)\) then \(\text{cof}(s)=s\) #Else if \(s=s_1+s_2\) with \(s_1\in T,s_2\in PT\) then \(\text{cof}(s)=\text{cof}(s_2)\) #Else if \(s=\psi_a(b)\) : ##If \(\text{cof}(b)=1\vee a\leq\text{cof}(b)\) then \(\text{cof}(s)=\omega\) ##Otherwise, \(\text{cof}(s)=\text{cof}(b)\) We let \(H(s) :\!\iff 0<\text{lev}(\text{lev}(s))\) Definition of \(\text{lev}(s)\) : #\(\text{lev}(0)=0\) #If \(s=s_1+s_2\) with \(s_1\in PT,s_2\in T\) then \(\text{lev}(s)=0\) #Else if \(s=\mu(a)\) then \(\text{lev}(s)=\psi_{\mu(0)}(a)\) #Else if \(s=\psi_a(b)\) : ##If \(H(a)\) : ###If \(\omega<\text{cof}(b) Standard form \(OT\): # \(0\in OT\) # For \(\alpha \in OT\), \(\mu(\alpha)\in OT\) # For \(m\geq 2\), \(\alpha_1,\ldots,\alpha_m\in OT\cap PT\) and \(\alpha_m\leq\ldots\leq\alpha_1\) then \(\alpha_1+\ldots+\alpha_m\in OT\) # For \(\kappa,\alpha\in OT\), \(\psi_\kappa(\alpha)\in OT\) iff: ## \(0<\text{lev}(\kappa)\) ## \(G_\kappa(\alpha)\leq\alpha\) ## \((\kappa\neq\Omega\wedge\kappa\neq V)\implies\alpha\neq 0\) ## \(\kappa=\mu(\beta) \implies \text{cof}(\beta)\leq\alpha\) ## \(\kappa=\psi_\pi(\beta) \wedge H(\pi) \implies \text{cof}(\beta)\leq\alpha\) Expansion We define the expansion function \(E(\alpha,n) : OT \times OT \to T\) : # If \(\alpha=\alpha_1+\alpha_2\) with \(\alpha_1\in PT,\alpha_2\in T\) then \(E(\alpha,n)=\alpha_1+E(\alpha_2,n)\) # Else if \(\alpha\in ST\wedge n=0\) then \(E(\alpha,n)=\text{pre}(n)\) # Else if \(0<\text{lev}(\alpha)\wedge n<\alpha\) then \(E(\alpha,n)=n\) # Else if \(\alpha=\psi_\kappa(\beta)\) : ## If \(\text{lev}(\kappa)=1\wedge \beta\in ST\): ### If \(n=0\), \(E(\alpha,0)=0\) ### Otherwise, \(E(\alpha,n)=\psi_\kappa(\text{pre}(\beta))+E(\psi_\kappa(\beta),\text{pre}(n))\) ## Else if \(\kappa=\mu(\delta)\wedge\text{cof}(\delta)=\beta\) then \(E(\alpha,n)=\mu(E(\delta,n))\) ## Else if \(\kappa=\psi_\pi(\delta)\wedge H(\pi)\wedge\text{cof}(\delta)=\beta\) then \(E(\alpha,n)=\psi_\pi(E(\delta,n))\) ## Else if \(\text{cof}(\beta)<\kappa\) then \(E(\alpha,n)=\psi_\kappa(E(\beta,n))\) ## Else if \(\kappa\leq\text{cof}(\beta)\) then \(E(\alpha,n)=\psi_\kappa(R(\beta,n))\), where \(R(\beta,n)=\begin{cases}0 & n=0 \\ E(\beta,\psi_{\text{cof}(\beta)}(R(\beta,\text{pre}(n)))) & \text{otherwise}\end{cases}\) We then define a standardization function \(S(a)\) with \(a\in T\) : # \(S(0)=0\) # \(S(\mu(b))=\mu(S(b))\) # If \(a=a_1+a_2\) with \(a_1\in PT,a_2\in \{0\}\cup T\) : ## If \(a_2=0\) then \(S(a)=S(a_1)\) ## Otherwise, \(S(a)=S(a_1)+S(a_2)\) # Else if \(a=\psi_b©\) ## If \(b=\mu(d)\wedge S©<\text{cof}(d)\) then \(S(a)=\mu(dS(c))\) ## Else if \(b=\psi_d(e)\wedge H(d)\wedge S©<\text{cof}(e)\) then \(S(a)=\psi_d(eS(c))\) ## Otherwise, \(S(a)=\psi_b(S©)\) Fundamental sequence system We finally define the fundamental sequence system \(\alphan\) as \(S(E(\alpha,n))\) under the restriction that \(\alpha,n\in OT\) and \(n<\text{cof}(\alpha)\) Large computable number : the Star We create a mapping from \(\mathbb{N}\) to \(OT\) : *\(N(0)=0\) *\(N(1)=1\) *For \(m\geq1\), \(N(m+1)=N(m)+1\) We also create a mapping \(\tau\) from \(\mathbb{N}\) to \(\text{OT}\) : *\(\tau(0)=0\) *\(\tau(n+1)=\mu(\tau(n))\) We define a version of the FGH for this ordinal notation, \(F_\alpha(n)\) with \(\alpha\in OT, n\in\mathbb{N}\), \(\alpha<\Omega\) and \(\text{cof}(\alpha)\leq\omega\) : *\(F_0(n)=n+1\) *If \(\alpha\in ST\) then \(F_\alpha(n)=F^n_{\text{pre}(\alpha)}(n)\), where \(F^n\) denotes iteration *Otherwise, \(F_\alpha(n)=F_{\alphaN(n)}(n)\) Finally, we define the Star as \(F_{S(\psi(\tau(10^{100})))}(10^{100})\). Assuming the well-foundedness of the ordinal notation system immediately implies the termination of the computation. Strength (Needless to say, assuming well-foundedness here) The strength of the system is currently unknown. Ecl1psed has put it beyond the limit of BMS as a whole. I personally doubt that claim, so analysis will have to be performed. I can however say with some confidence that it is stronger than Rathjen's OCF based on a weakly compact cardinal and maybe stronger than a \(\Pi_\omega\)-reflection OCF, such as Stegert's or Arai's. However, I would still place it below TON (assuming well-foundedness) and Loader's function. I would also like to address this question from a definition standpoint : what in the notation makes the notation strong? My immediate answer is the lev function. The lev function gives a "regularity degree" of a given STON expression ; intuitively, how many times it can be put inside of a psi subscript before becoming singular. A concrete example of why lev makes the notation strong is \(\psi_V(\omega)\). One would expect it to be a simple limit, but the lev function says otherwise : rule 4.1.5.6 gives it level 2,which not only makes it regular (and thus not an ordinary limit), but "more regular" than anything below it. And according to rule 4.4 of E, the limit of \(\psi_V(n)\) for \(n<\omega\) is in fact \(\psi_{\psi_V(\omega)}(\omega)\). So we """arbitrarily""" gave a big boost in power to \(\psi_V(\omega)\), and looking at its behaviour, it's quite similar to the least inaccessible cardinal I. Further analysis leads me to believe this is the best comparison. Even below the extensions of STON 2, this behaviour of lev makes some values really powerful just by increasing their level by 1. When we get to mu, these levels get uncountable, pseudo-inaccessible and whatever other pseudo-properties i could feel like coining. I hope you realize why this leads us to think the notation is strong. Long standard forms This is just a little area to showcase how long and crazy the standard forms get in this extension. I will be going over a few well-known ordinals and their believed equivalent in STON. Last three expressions in the left column use Rathjen's OCF Proofs Assumptions : *\(<\) is transitive *\(sn'I was unable to prove this without an extremely long case exhaustion (which is just not worth it for this kind of work). Instead I just made an assumption that was reasonable according to the definition of lev. Recall, the function lev() is meant to give a "degree of regularity" which is supposed to indicate how much a given expression can be collapsed as a subscript of \(\psi\). Therefore this assumptions falls in line with what lev is intended to do. ' We work in OT and, keeping with convention, we always have \(s_1,t_1\in PT,s_2,t_2\in T\) unless otherwise mentioned. We will use the following construction of \(T\) to perform induction : *\(T_0=\{0\}\) *\(T_{n+1}= T_n\cup \{a+b,\psi_a(b),\mu(a)|a,b\in T_n\}\) *\(T = \bigcup\limits_{n\in\omega} T_n\) We also use a complementary construction of \(OT\) : *\(OT_0 = T_0\) *\(OT_{n+1}\) is equal to \(T_{n+1}\) with the additional restrictions of \(OT\) *\(OT = \bigcup\limits_{n\in\omega} OT_n\) 'Theorem 1 ': \(<\) is irreflexive Proof : We show that there is no \(s\) such that \(s Base case : Trivial Inductive case : For any \(t\in T_{n+1}\): *If \(t=t_1+t_2\) then \(\text{lev}(t)=0\) *If \(t=\mu(\alpha)\) then \(t Base case : Trivial Inductive case : For any \(t\in T_{n+1}\): *If \(t=t_1+t_2\) then \(\text{lev}(t)=0\) *If \(t=\mu(\alpha)\) then \(t<\Omega \iff t Base case : Trivial Inductive case : For any \(t\in T_{n+1}\): *If \(t=\psi_\kappa(\alpha)\) : by Lemma 2.3, \(\Omega\leq\kappa\) **If \(\kappa=\Omega\), \(t<1 \iff \alpha<0\) which is impossible **Else if \(\text{lev}(\kappa)=\text{lev}(\Omega)\) then \(t<1 \iff \kappa<\Omega\) which contradicts \(\Omega\leq\kappa\) **Else if \(H(\kappa)\) then \(t<1 \iff t<\Omega \iff \kappa Base case : Trivial Inductive case : For \(s,t\in OT_{n+1}\) : Neither \(s\) or \(t\) can be 0, because in the former case, \(s+1 \notin OT_n\), and in the latter case, \(s Base case : Trivial Inductive case : For \(t\in OT_{n+1}\) : If \(t=0,t=1\) or \(0<\text{lev}(t)\), \(\text{cof}(t)\leq t \iff t\leq t\) which is always true. If \(t=t_1+t_2\), \(\text{cof}(t)\leq t \iff \text{cof}(t_2)\leq t_1+t_2\). By inductive hypothesis, \(\text{cof}(t_2)\leq t_2\). We either have \(t_2\leq t_1+t_2\) or \(t_1+t_2